package algorithms.roughgarden.part2.dynamicprogramming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

import algorithms.roughgarden.part2.clustering.Edge;



public class Main {
	private static final String INPUT_FILE_NAME = "knapsack1.txt";
	private static final String DELIMITER=" ";
	private static int[][] memoArray;
	private static int knapsackSize;
	private static int noOfItems;

	public static void main(String[] args) throws IOException {
		InputStream is = Main.class.getResourceAsStream(INPUT_FILE_NAME);
		BufferedReader br = new BufferedReader(new InputStreamReader(is));
		String str;
		str = br.readLine();
		String[] strArr = str.split(DELIMITER);
		knapsackSize = Integer.parseInt(strArr[0]);
		noOfItems = Integer.parseInt(strArr[1]);
		memoArray = new int[noOfItems+1][knapsackSize+1];
		int itemIdx=0   , weightIdx=0;
		/*	int[] arr = new int[5];
		for(int i=0;i<5;){
			arr[i]=i++;
		}
		for(int i=0;i<5;i++){
			System.out.println(arr[i]);
		}
		System.out.println("AFTER");
		for(int i=0;i<4;){
			arr[i]=arr[i++];
		}

		for(int i=0;i<5;i++){
			System.out.println(arr[i]);
		}*/
		while((str = br.readLine())!=null){
			strArr = str.split(DELIMITER);
			itemIdx++;
			weightIdx = 0;
			while(weightIdx <= knapsackSize){
				memoArray[itemIdx][weightIdx] = getMaxUnderweight(Integer.parseInt(strArr[1]), Integer.parseInt(strArr[0]), itemIdx, weightIdx);
				weightIdx++;
			}
		}
		System.out.println(memoArray[noOfItems][knapsackSize]);
	}
	private static int getMaxUnderweight(int currentItemWeight, int currentItemValue, int itemNumber, int currentWeightLimit){
		int maxWeight = memoArray[itemNumber-1][currentWeightLimit];
		if(currentItemWeight<=currentWeightLimit){
			maxWeight = Math.max(maxWeight, currentItemValue+memoArray[itemNumber-1][currentWeightLimit-currentItemWeight]);
		}
		return maxWeight;
	}

}
